|
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した。 == 概要 == 長さ11の文字列 を例に取って説明する。先頭から一文字ずつ削ってみればわかるように、この文字列は "abracadabra", "bracadabra", "racadabra", ……, "ra", "a" という11の接尾辞を持つと考えられる。この11の接尾辞を、それぞれの開始位置(1～11)とともに配列に順次格納し、接尾辞について辞書順に並べ替えると以下のようになる。表中の最長共通接頭辞（LCP）は、直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合の最大文字数。 元の文字列があれば、接尾辞の開始位置を指定することですべての接尾辞を余すことなく得ることができる。この接尾辞を辞書順に並べたときの開始位置の配列が接尾辞配列となる。 "abracadabra"に対する接尾辞配列は、表のように、(11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3) となる。接尾辞 "a" の開始位置は11で、接尾辞 "abra" の開始位置は8だからである。 "abracadabra"に対して、12番目の接尾辞として空文字を考えることができる。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「接尾辞配列」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Suffix array 」があります。 スポンサード リンク
|